1
計數的基礎
MATH002Lesson 6
00:00
計數是透過邏輯結構來判斷有限集合大小的藝術,無需費力地逐一清點。藉由這種方法,我們可以解決從簡單的菜單組合到複雜的密碼學排列等各種問題。

"或"與"且"的邏輯

兩個核心原則支撐著整個組合數學領域。其應用完全取決於我們是否將任務視為從多個類別中做單一選擇,還是作為一系列連續的選擇。

加法原理(求和規則)

若集合 $X$ 被劃分為互不重疊的子集 $X_1, X_2, \dots, X_n$,則總元素數 $|X|$ 等於這些子集大小的總和:

$$|X| = |X_1| + |X_2| + \dots + |X_n|$$

類比: 在凱的速食餐廳點餐時,你可以從主菜選一份三明治,或從開胃菜選一種,但不能兩者都選;你只能挑選其中一個項目。

乘法原理(乘積規則)

若某項活動包含 $t$ 個連續步驟,其中第 $i$ 步有 $n_i$ 種可能結果,則完成該任務的總方式數等於各步可能性的乘積:

$$N = n_1 \times n_2 \times \dots \times n_t$$

類比: 設定一輛「大貨車」的配置。你必須選擇一台引擎(5種選項)與一種駕駛室款式(3種選項)。總共的組合數為 $5 \times 3 = 15$ 種。

程式實作與複雜度

在電腦科學中,這些原理體現在迴圈結構上。順序執行的迴圈代表加法原理,而巢狀迴圈則代表乘法原理。

// 加法原理(執行次數:m + n)
for i = 1 到 m:println(i)
for j = 1 到 n:println(j)

// 乘法原理(執行次數:m × n)
for i = 1 到 m:
for j = 1 到 n:
println(i, j)
🎯 核心原則
根據關鍵字區分:"或"代表加法(互斥的選擇),而"且"或"連續"則代表乘法(序列中的獨立步驟)。